﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace grafo {
    public class Grafo {
        public class CattivaCfcException : Exception {
            public uint[] Cfc { get; private set; }

            public CattivaCfcException(string message, uint[] cfc) : base(message) {
                Cfc = cfc;
            }
        }

        public bool[,] Matrice { get; private set; }
        public uint Dim { get; private set; }
        public List<uint> NodiAttivi { get; private set; }

        public Grafo(bool[,] m, uint dim) {
            Matrice = m;
            Dim = dim;
            NodiAttivi = new List<uint>();
            for (uint i = 0; i < dim; i++)
                NodiAttivi.Add(i);
        }

        public bool AddArco(uint a, uint b) {
            if (a > Dim || b > Dim)
                throw new ArgumentException("Nodi non presenti");
            if (!Matrice[a, b]) {
                Matrice[a, b] = true;
                return true;
            }
            if (!Matrice[b, a]) {
                Matrice[b, a] = true;
                return true;
            }
            return false;
        }

        //rimuove tutti i cappi del grafo
        public void RimuoviCappi() {
            for (var i = 0; i < Dim; i++)
                Matrice[i, i] = false;
        }

        //calcola il grado del nodo n
        public uint GradoNodo(uint n) {
            uint c = 0;
            for (var i = 0; i < Dim; i++) {
                if (Matrice[n, i])
                    c++;
            }
            return c;
        }

        //calcola il grado del grafo
        public uint GradoGrafo() {
            uint c = 0;
            for (var i = 0; i < Dim; i++) {
                for (var j = 0; j < Dim; j++) {
                    if (Matrice[i, j])
                        c++;
                }
            }
            return c;
        }

        //dice se la list contiene già elem
        private static bool Contains(IEnumerable<uint[]> list, IList<uint> elem) {
            return elem.Count == 2
                       ? list.Where(u => u.Length != 3).Any(u => elem[0] == u[1] && elem[1] == u[0])
                       : list.Where(u => u.Length != 2).Any(
                           u => u.Contains(elem[0]) && u.Contains(elem[1]) && u.Contains(elem[2]));
        }

        //trova tutte le cfc
        public List<uint[]> CFC() {
            var a = new List<uint[]>();
            for (uint i = 0; i < Dim; i++) {
                for (uint j = 0; j < Dim; j++) {
                    if (i == j)
                        continue;
                    if (!Matrice[i, j])
                        continue;
                    if (Matrice[j, i]) {
                        var temp = new uint[2];
                        temp[0] = i;
                        temp[1] = j;
                        if (!Contains(a, temp))
                            a.Add(temp);
                    }
                    for (uint k = 0; k < Dim; k++) {
                        if ((!Matrice[j, k] && !Matrice[k, j]) || (!Matrice[i, k] && !Matrice[k, i]))
                            continue;
                        var temp = new uint[3];
                        temp[0] = i;
                        temp[1] = j;
                        temp[2] = k;
                        if (!Contains(a, temp))
                            a.Add(temp);
                    }
                }
            }
            return a;
        }

        //dice se una cfc ha almeno 2 nodi ponte
        private void IsCfcRedundant(uint[] cfc) {
            var count = 0;
            var ponti = new List<uint>();
            foreach (var b in cfc) {
                for (uint i = 0; i < Dim; i++) {
                    if (cfc.Contains(i) || (!Matrice[b, i] && !Matrice[i, b]) || ponti.Contains(b))
                        continue;
                    var grado = cfc.Aggregate<uint, uint>(0, (current, u) => current + GradoNodo(u));
                    if (grado >= 2*Dim)
                        throw new CattivaCfcException("Non esiste cammino - grado 2n", cfc);
                    count++;
                    ponti.Add(b);
                    if (count == 2)
                        return;
                }
            }
            if (count > 0)
                throw new CattivaCfcException("Non esiste cammino - nodi ponte " + count, cfc);
        }

        //rimuove inOrder le cfc
        public void RemoveCfc(ref List<uint[]> cfcs, uint[] daRimuovere) {
            if (cfcs.Count <= 0)
                return;
            DeleteCfc(daRimuovere);
            RimuoviCappi();
            cfcs = CFC();
        }

        //seleziona la miglior cfc da rimuovere
        public bool SelectCfc(ICollection<uint[]> cfcs, out uint[] currentCfc) {
            currentCfc = new uint[0];
            if (cfcs.Count == 0)
                return false;
            var temp = TrovaTriangoli(cfcs);
            if (temp.Count != 0) {
                currentCfc = MinorGradoTotTrinagolo(temp);
                return true;
            }
            //ASSERT: cfcs contiene solo coppie
            temp = MinorGradoTotCoppie(cfcs);
            currentCfc = PiuSbilanciata(temp);
            return true;
        }

        //trova la cfc + sbilanciata (solo cfc coppie)
        private uint[] PiuSbilanciata(IEnumerable<uint[]> temp) {
            var gradoMax = uint.MinValue;
            var result = new uint[0];
            foreach (var uintse in temp) {
                var delta = (uint) (Math.Abs(GradoNodo(uintse[0]) - GradoNodo(uintse[1])));
                if (delta < gradoMax)
                    continue;
                gradoMax = delta;
                result = uintse;
            }
            return result;
        }

        //trova la cfc-triangolo col minor grado totale
        private uint[] MinorGradoTotTrinagolo(IEnumerable<uint[]> temp) {
            var gradoMin = uint.MaxValue;
            var result = new uint[0];
            foreach (var uintse in temp) {
                gradoMin = Valueted(gradoMin, uintse);
                result = uintse;
            }
            return result;
        }

        //trova la cfc-coppia con minor grado totale
        private List<uint[]> MinorGradoTotCoppie(IEnumerable<uint[]> temp) {
            var gradoMin = uint.MaxValue;
            foreach (var uintse in temp) {
                IsCfcRedundant(uintse);
                gradoMin = Valueted(gradoMin, uintse);
            }
            return
                temp.Where(uintse => uintse.Aggregate<uint, uint>(0, (current, u) => current + GradoNodo(u)) == gradoMin)
                    .ToList();
        }

        private uint Valueted(uint gradoMin, IEnumerable<uint> uintse) {
            var t = uintse.Aggregate<uint, uint>(0, (current, u) => current + GradoNodo(u));
            if (t >= gradoMin)
                return gradoMin;
            gradoMin = t;
            return gradoMin;
        }

        //trova tutti i triangoli nella lista delle cfc
        private List<uint[]> TrovaTriangoli(IEnumerable<uint[]> cfcs) {
            var res = new List<uint[]>();
            foreach (var uintse in cfcs.Where(uintse => uintse.Length == 3)) {
                IsCfcRedundant(uintse);
                res.Add(uintse);
            }
            return res;
        }

        //cancella la cfc
        private void DeleteCfc(uint[] cfc) {
            var daSistemare = new List<uint[]>();
            for (uint i = 0; i < Dim; i++) {
                for (uint j = 0; j < Dim; j++) {
                    if ((!cfc.Contains(i) && !cfc.Contains(j)))
                        continue;
                    if ((!Matrice[i, j] && !Matrice[j, i]) || (cfc.Contains(j) && cfc.Contains(i))) {
                        Matrice[i, j] = false;
                        Matrice[j, i] = false;
                        continue;
                    }
                    var temp = new uint[2];
                    temp[0] = i;
                    temp[1] = j;
                    daSistemare.Add(temp);
                    Matrice[i, j] = false;
                    Matrice[j, i] = false;
                }
            }
            //SISTEMA GLI ARCHI CHE ENTRAVANO NELLA CFC RIMOSSA
            SistemaArchi(cfc, daSistemare);

            /*foreach (var uintse in daSistemare) {
                uint nodoEliminato;
                var flag = false;
                foreach (var uintse1 in daSistemare) {
                    if (uintse1 == uintse)
                        continue;
                    // if(Matrice[uintse,uintse1])
                }
                nodoEliminato = cfc.Contains(uintse[0]) ? uintse[0] : uintse[1];
            }*/
        }

        //dice se il grafo contiene nodi di grado 1
        public bool AreThereNodesGrade1() {
            for (uint i = 0; i < Dim; i++) {
                if (GradoNodo(i) == 1)
                    return true;
            }
            return false;
        }

        //controlla che la somma dei gradi dei nodi sia pari
        public bool IsSumGradesEven() {
            return GradoGrafo()%2 == 0;
        }

        //controllo ogni nodo con grado>2 sia connesso ad un altro nodo di grado >2
        public bool CheckNodiP2() {
            var ris = false;
            for (uint i = 0; i < Dim; i++) {
                var nodiAdiacenti = NodiAdiacenti(i);
                foreach (var u in nodiAdiacenti.Where(u => GradoNodo(u) > 2))
                    ris = true;
                if (ris == false)
                    return false;
            }
            return ris;
        }

        //controllo che il numero dei nodi con grado >2 sia pari
        public bool AreEvenNodeP2() {
            uint count = 0;
            for (uint i = 0; i < Dim; i++) {
                if (GradoNodo(i) > 2)
                    count++;
            }
            return count%2 == 0;
        }

        //cerca la coppia a minor grado totale
        private uint[] CoppiaGradoMinore(IEnumerable<uint[]> coppie) {
            var min = uint.MaxValue;
            var res = new uint[2];
            foreach (var uintse in coppie) {
                var temp = GradoNodo(uintse[0]) + GradoNodo(uintse[1]);
                if (temp >= min)
                    continue;
                res = uintse;
                min = temp;
            }
            return res;
        }

        //trova la coppia più sbilanciata
        private uint[] CoppiaPiuSbilanciata(IEnumerable<uint[]> coppie) {
            var max = uint.MinValue;
            var res = new uint[2];
            foreach (var re in coppie) {
                var temp = (uint) (Math.Abs(GradoNodo(re[0]) - GradoNodo(re[1])));
                if (temp <= max)
                    continue;
                max = temp;
                res = re;
            }
            return res;
        }

        //trova tutti i nodi adiacenti a un nodo
        private IEnumerable<uint> NodiAdiacenti(uint nodo) {
            var ris = new List<uint>();
            for (uint i = 0; i < Dim; i++) {
                if ((Matrice[i, nodo] || Matrice[nodo, i]) && i != nodo)
                    ris.Add(i);
            }
            return ris;
        }

        //trova tutti i nodi adiacenti ad 1 coppia di nodi
        private IEnumerable<uint> NodiAdiacenti(IEnumerable<uint> coppia) {
            var ris = new List<uint>();
            ris = coppia.Aggregate(ris, (current, u) => current.Concat(NodiAdiacenti(u)).ToList());
            return ris;
        }

        //trova la coppia di nodi con il minor grado di adiacenza
        private uint[] CoppiaConMinorGradiAdiacenti(IEnumerable<uint[]> coppie) {
            var min = uint.MaxValue;
            var res = new uint[2];
            foreach (var uintse in coppie) {
                var temp = NodiAdiacenti(uintse);
                var temp2 = temp.Aggregate<uint, uint>(0, (current, u) => current + GradoNodo(u));
                if (temp2 >= min)
                    continue;
                min = temp2;
                res = uintse;
            }
            return res;
        }

        //trova le coppie di nodi con grado >2
        private List<uint[]> FindCoppieNodiGradoPiu2() {
            var res = new List<uint[]>();
            for (uint i = 0; i < Dim; i++) {
                if (GradoNodo(i) <= 2)
                    continue;
                var nodiAdiacenti = NodiAdiacenti(i);
                foreach (var u in nodiAdiacenti) {
                    if (u <= 2)
                        continue;
                    var coppia = new uint[2];
                    coppia[0] = i;
                    coppia[1] = u;
                    res.Add(coppia);
                }
            }
            return res;
        }

        //rimuove una coppia di nodi con grado >2
        private void RemoveAPair(uint[] coppia) {
            var archiDaSistemare = new List<uint[]>();
            for (uint i = 0; i < Dim; i++) {
                uint[] temp;
                if (Matrice[i, coppia[0]] || Matrice[coppia[0], i]) {
                    temp = new uint[2];
                    temp[0] = i;
                    temp[1] = coppia[0];
                    archiDaSistemare.Add(temp);
                    continue;
                }
                if (!Matrice[i, coppia[1]] && !Matrice[coppia[1], i])
                    continue;
                temp = new uint[2];
                temp[0] = i;
                temp[1] = coppia[1];
                archiDaSistemare.Add(temp);
            }
            SistemaArchi(coppia, archiDaSistemare);
        }

        private void SistemaArchi(uint[] coppia, IEnumerable<uint[]> archiDaSistemare) {
            var nodiPonte =
                archiDaSistemare.Select(uintse => coppia.Contains(uintse[0]) ? uintse[1] : uintse[0]).ToList();
            foreach (var u in nodiPonte) {
                var sistemato = false;
                foreach (var u1 in nodiPonte) {
                    //se quel nodo ponte non ha già nessun arco che lo collega a un altro nodo ponte, lo collego a quest'ultimo e l'ho sistemato
                    if (Matrice[u, u1] || Matrice[u1, u] || u1 == u)
                        continue;
                    Matrice[u, u1] = true;
                    sistemato = true;
                    break;
                }
                if (sistemato == false) { //se è già collegato con almeno 1 arco a tutti gli altri nodi ponte
                    foreach (var u1 in nodiPonte) {
                        if (!Matrice[u, u1] && Matrice[u1, u] && u1 != u) { //se è collegato con 1 solo arco ad 1 altro nodo ponte, lo collego a questo ed ho finito
                            Matrice[u, u1] = true;
                            sistemato = true;
                            break;
                        }
                        if (Matrice[u1, u] || !Matrice[u, u1] || u1 == u)
                            continue;
                        //se è collegato con 1 solo arco ad 1 altro nodo ponte, lo collego a questo ed ho finito
                        Matrice[u1, u] = true;
                        sistemato = true;
                        break;
                    }
                    //se son qui, vuol dire ke è collegato a tutti gli altri nodi-ponte con già 2 archi, quindi è a posto ed ho finito
                }
            }
            //tolgo gli archi interni alla cfc 
            foreach (var u in coppia) {
                foreach (var u1 in coppia) {
                    Matrice[u1, u] = false;
                    Matrice[u, u1] = false;
                }
            }
            //tolgo i nodi
            foreach (var u in coppia)
                NodiAttivi.Remove(u);
        }

        /* public void StampaTest() {
            for (var i = 0; i < 5; i++) {
                for (var j = 0; j < 5; j++)
                    Console.Write(Matrice[i, j] ? " " : "x");
                Console.WriteLine();
            }
        }*/

        /*public void Main() {
            var m = new bool[6,6];
            for (var i = 0; i < m.Length; i++) {
                for (var j = 0; j < m.Length; j++)
                    m[i, j] = false;
            }
            m[0, 1] = true;
            m[1, 2] = true;
            m[1, 4] = true;
            m[2, 0] = true;
            m[3, 2] = true;
            m[4, 5] = true;
            m[5, 3] = true;
            var test = new Grafo(m, 6);
            test.StampaTest();
        }*/
    }
}